home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / gzpath.h < prev    next >
C/C++ Source or Header  |  1997-03-19  |  11KB  |  294 lines
  1. /* Copyright (C) 1989, 1995, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gzpath.h */
  20. /* Private representation of paths for Ghostscript library */
  21. /* Requires gxfixed.h */
  22. #include "gxpath.h"
  23. #include "gsstruct.h"            /* for extern_st */
  24.  
  25. /*
  26.  * Paths are represented as a linked list of line or curve segments,
  27.  * similar to what pathforall reports.
  28.  */
  29.  
  30. /*
  31.  * Define path segment types: segment start, line, or Bezier curve.
  32.  * We have a special type for the line added by closepath.
  33.  */
  34. typedef enum {
  35.     s_start,
  36.     s_line,
  37.     s_line_close,
  38.     s_curve
  39. } segment_type;
  40. /* Define the common structure for all segments. */
  41. #define segment_common\
  42.     segment *prev;\
  43.     segment *next;\
  44.     ushort /*segment_type*/ type;\
  45.     ushort /*segment_notes*/ notes;\
  46.     gs_fixed_point pt;        /* initial point for starts, */\
  47.                     /* final point for others */
  48.  
  49. /* Forward declarations for structure types */
  50. #ifndef segment_DEFINED
  51. #  define segment_DEFINED
  52. typedef struct segment_s segment;
  53. #endif
  54. typedef struct subpath_s subpath;
  55.  
  56. /*
  57.  * Define a generic segment.  This is never instantiated,
  58.  * but we define a descriptor anyway for the benefit of subclasses.
  59.  */
  60. struct segment_s {
  61.     segment_common
  62. };
  63. #define private_st_segment()    /* in gxpath.c */\
  64.   gs_private_st_ptrs2(st_segment, struct segment_s, "segment",\
  65.     segment_enum_ptrs, segment_reloc_ptrs, prev, next)
  66.  
  67. /* Line segments have no special data. */
  68. typedef struct {
  69.     segment_common
  70. } line_segment;
  71. #define private_st_line()    /* in gxpath.c */\
  72.   gs_private_st_suffix_add0(st_line, line_segment, "line",\
  73.     line_enum_ptrs, line_reloc_ptrs, st_segment)
  74.  
  75. /* Line_close segments are for the lines appended by closepath. */
  76. /* They point back to the subpath being closed. */
  77. typedef struct {
  78.     segment_common
  79.     subpath *sub;
  80. } line_close_segment;
  81. #define private_st_line_close()    /* in gxpath.c */\
  82.   gs_private_st_suffix_add1(st_line_close, line_close_segment, "close",\
  83.     close_enum_ptrs, close_reloc_ptrs, st_segment, sub)
  84.  
  85. /*
  86.  * We use two different representations for curve segments: one defined by
  87.  * two endpoints (p0, p3) and two control points (p1, p2), and one defined
  88.  * by two sets of parametric cubic coefficients (ax ... dy).  Here is how
  89.  * they are related (v = x or y).  We spell out some multiplies by 3 for
  90.  * the benefit of compilers too simple to optimize this.
  91.  */
  92. #define curve_points_to_coefficients(v0, v1, v2, v3, a, b, c, t01, t12)\
  93.   (/*d = (v0),*/\
  94.    t01 = (v1) - (v0), c = (t01 << 1) + t01,\
  95.    t12 = (v2) - (v1), b = (t12 << 1) + t12 - c,\
  96.    a = (v3) - b - c - (v0))
  97. /*
  98.  * or conversely
  99.  */
  100. #define curve_coefficients_to_points(a, b, c, d, v1, v2, v3)\
  101.   (/*v0 = (d),*/\
  102.    v1 = (d) + ((c) / 3),\
  103.    v2 = v1 + (((b) + (c)) / 3),\
  104.    v3 = (a) + (b) + (c) + (d))
  105.  
  106. /* Curve segments store the control points. */
  107. typedef struct {
  108.     segment_common
  109.     gs_fixed_point p1, p2;
  110. } curve_segment;
  111. #define private_st_curve()    /* in gxpath.c */\
  112.   gs_private_st_composite_only(st_curve, curve_segment, "curve",\
  113.     segment_enum_ptrs, segment_reloc_ptrs)
  114.  
  115. /*
  116.  * Define a start segment.  This serves as the head of a subpath.
  117.  * The closer is only used temporarily when filling,
  118.  * to close an open subpath.
  119.  */
  120. struct subpath_s {
  121.     segment_common
  122.     segment *last;            /* last segment of subpath, */
  123.                     /* points back to here if empty */
  124.     int curve_count;        /* # of curves */
  125.     line_close_segment closer;
  126.     char/*bool*/ is_closed;        /* true if subpath is closed */
  127. };
  128. #define private_st_subpath()    /* in gxpath.c */\
  129.   gs_private_st_suffix_add1(st_subpath, subpath, "subpath",\
  130.     subpath_enum_ptrs, subpath_reloc_ptrs, st_segment, last)
  131.  
  132. /* Test whether a subpath is a rectangle; if so, also return */
  133. /* the start of the next subpath. */
  134. bool gx_subpath_is_rectangle(P3(const subpath *pstart, gs_fixed_rect *pbox,
  135.                 const subpath **ppnext));
  136.  
  137. /* Curve manipulation */
  138.  
  139. /* Return the smallest value k such that 2^k segments will approximate */
  140. /* the curve to within the desired flatness. */
  141. int    gx_curve_log2_samples(P4(fixed, fixed, const curve_segment *, fixed));
  142.  
  143. /* Return up to 2 values of t which split the curve into monotonic parts. */
  144. int    gx_curve_monotonic_points(P5(fixed, fixed, fixed, fixed, double [2]));
  145.  
  146. /* Split a curve at an arbitrary value of t. */
  147. void    gx_curve_split(P6(fixed, fixed, const curve_segment *, double,
  148.               curve_segment *, curve_segment *));
  149.  
  150. /* Flatten a partial curve by sampling (internal procedure). */
  151. int    gx_flatten_sample(P4(gx_path *, int, curve_segment *, segment_notes));
  152.  
  153. /* Initialize a cursor for rasterizing a monotonic curve. */
  154. typedef struct curve_cursor_s {
  155.         /* Following are set at initialization */
  156.     int k;            /* 2^k segments */
  157.     gs_fixed_point p0;    /* starting point */
  158.     const curve_segment *pc;  /* other points */
  159.     fixed a, b, c;        /* curve coefficients */
  160.     double da, db, dc;    /* scaled double versions of a, b, c */
  161.     bool double_set;    /* true if da/b/c set */
  162.     int fixed_limit;    /* can do in fixed point if t <= limit */
  163.         /* Following are updated dynamically. */
  164.     struct ccc_ {        /* one-element cache */
  165.       fixed ky0, ky3;    /* key (range) */
  166.       fixed xl, xd;        /* value */
  167.     } cache;
  168. } curve_cursor;
  169. void    gx_curve_cursor_init(P5(curve_cursor *prc, fixed x0, fixed y0,
  170.                 const curve_segment *pc, int k));
  171.  
  172. /* Return the value of X at a given Y value on a monotonic curve. */
  173. /* y must lie between prc->p0.y and prc->pt.y. */
  174. fixed    gx_curve_x_at_y(P2(curve_cursor *prc, fixed y));
  175.  
  176. /*
  177.  * The path state flags reflect the most recent operation on the path
  178.  * as follows:
  179.  *    Operation    position_valid    subpath_open    is_drawing
  180.  *    newpath        no        no        no
  181.  *    moveto        yes        yes        no
  182.  *    lineto/curveto    yes        yes        yes
  183.  *    closepath    yes        no        no
  184.  * If position_valid is true, outside_range reflects whether the most
  185.  * recent operation went outside of the representable coordinate range.
  186.  * If this is the case, the corresponding member of position (x and/or y)
  187.  * is min_fixed or max_fixed, and outside_position is the true position.
  188.  */
  189. /*
  190.  */
  191. typedef enum {
  192.     /* Individual flags.  These may be or'ed together, per above. */
  193.   psf_position_valid = 1,
  194.   psf_subpath_open = 2,
  195.   psf_is_drawing = 4,
  196.   psf_outside_range = 8,
  197.     /* Values stored by path building operations. */
  198.   psf_last_newpath = 0,
  199.   psf_last_moveto = psf_position_valid | psf_subpath_open,
  200.   psf_last_draw = psf_position_valid | psf_subpath_open | psf_is_drawing,
  201.   psf_last_closepath = psf_position_valid
  202. } gx_path_state_flags;
  203. /*
  204.  * Individual tests
  205.  */
  206. #define path_position_valid(ppath)\
  207.   (((ppath)->state_flags & psf_position_valid) != 0)
  208. #define path_subpath_open(ppath)\
  209.   (((ppath)->state_flags & psf_subpath_open) != 0)
  210. #define path_is_drawing(ppath)\
  211.   (((ppath)->state_flags & psf_is_drawing) != 0)
  212. #define path_outside_range(ppath)\
  213.   (((ppath)->state_flags & psf_outside_range) != 0)
  214. /*
  215.  * Composite tests
  216.  */
  217. #define path_last_is_moveto(ppath)\
  218.   (((ppath)->state_flags & ~psf_outside_range) == psf_last_moveto)
  219. #define path_position_in_range(ppath)\
  220.   (((ppath)->state_flags & (psf_position_valid + psf_outside_range)) ==\
  221.    psf_position_valid)
  222. #define path_start_outside_range(ppath)\
  223.   ((ppath)->state_flags != 0 &&\
  224.    ((ppath)->start_flags & psf_outside_range) != 0)
  225. /*
  226.  * Updating operations
  227.  */
  228. #define path_update_newpath(ppath)\
  229.   ((ppath)->state_flags = psf_last_newpath)
  230. #define path_update_moveto(ppath)\
  231.   ((ppath)->state_flags = (ppath)->start_flags = psf_last_moveto)
  232. #define path_update_draw(ppath)\
  233.   ((ppath)->state_flags = psf_last_draw)
  234. #define path_update_closepath(ppath)\
  235.   ((ppath)->state_flags = psf_last_closepath)
  236. #define path_set_outside_position(ppath, px, py)\
  237.   ((ppath)->outside_position.x = (px),\
  238.    (ppath)->outside_position.y = (py),\
  239.    (ppath)->state_flags |= psf_outside_range)
  240.  
  241. /* Here is the actual structure of a path. */
  242. struct gx_path_s {
  243.     gs_memory_t *memory;
  244.     gs_fixed_rect bbox;        /* bounding box (in device space) */
  245.     segment *box_last;        /* bbox incorporates segments */
  246.                     /* up to & including this one */
  247.     subpath *first_subpath;
  248.     subpath *current_subpath;
  249.     int subpath_count;
  250.     int curve_count;
  251.     gs_fixed_point position;    /* current position */
  252.     gs_point outside_position;    /* position if outside_range is set */
  253.     gs_point outside_start;        /* outside_position of last moveto */
  254.     byte/*gx_path_state_flags*/ start_flags;    /* flags of moveto */
  255.     byte/*gx_path_state_flags*/ state_flags;    /* (see above) */
  256.     byte/*bool*/ bbox_set;        /* true if setbbox is in effect */
  257.     byte/*bool*/ shares_segments;    /* if true, this path shares its */
  258.                     /* segment storage with the one in */
  259.                     /* the previous saved graphics state */
  260. };
  261. extern_st(st_path);
  262. #define public_st_path()    /* in gxpath.c */\
  263.   gs_public_st_ptrs3(st_path, gx_path, "path",\
  264.     path_enum_ptrs, path_reloc_ptrs, box_last, first_subpath, current_subpath)
  265. #define st_path_max_ptrs 3
  266.  
  267. /* Path enumeration structure */
  268. struct gs_path_enum_s {
  269.     const segment *pseg;
  270.     const gs_state *pgs;
  271.     const gx_path *path;    /* path being enumerated */
  272.     gx_path *copied_path;    /* if the path was copied, this is the */
  273.                 /* the same as path, to be released */
  274.                 /* when done enumerating */
  275.     bool moveto_done;    /* have we reported a final moveto yet? */
  276.     segment_notes notes;    /* notes from most recent segment */
  277. };
  278. #define private_st_path_enum()    /* in gxpath2.c */\
  279.   gs_private_st_ptrs4(st_gs_path_enum, gs_path_enum, "gs_path_enum",\
  280.     path_enum_enum_ptrs, path_enum_reloc_ptrs, pseg, pgs, path, copied_path)
  281.  
  282. /* Macros equivalent to a few heavily used procedures. */
  283. /* Be aware that these macros may evaluate arguments more than once. */
  284. #define gx_path_current_point_inline(ppath,ppt)\
  285.  ( !path_position_valid(ppath) ? gs_note_error(gs_error_nocurrentpoint) :\
  286.    ((ppt)->x = ppath->position.x, (ppt)->y = ppath->position.y, 0) )
  287. /* ...rel_point rather than ...relative_point is because */
  288. /* some compilers dislike identifiers of >31 characters. */
  289. #define gx_path_add_rel_point_inline(ppath,dx,dy)\
  290.  ( !path_position_in_range(ppath) || ppath->bbox_set ?\
  291.    gx_path_add_relative_point(ppath, dx, dy) :\
  292.    (ppath->position.x += dx, ppath->position.y += dy,\
  293.     path_update_moveto(ppath), 0) )
  294.